#include <stdio.h>
#include <assert.h>


#define  TYPE   int
#define  SIZE   10


int Partition(TYPE *array, int low, int high);
int PartitionVersion2(TYPE *array, int low, int high);

int GetMiddle(TYPE *array, int low, int high);
void swap(TYPE * num1, TYPE *num2);
void QuickSort(TYPE *array, int low, int high);
void Print(TYPE *array, int low, int high);


int main()
{
    TYPE array[SIZE];
    int index;

    for (index = 0; index < SIZE; index++)
        scanf("%d", &array[index]);
    Print(array, 0, SIZE - 1);

    QuickSort(array, 0, SIZE - 1);

    printf("After it been sorted :\n");
    Print(array, 0, SIZE - 1);

}

void Print(TYPE *array, int low, int high)
{
    int index = low;
    for (; index <= high; index++)
        printf("%d  ", array[index]);
    printf("\n");


}
void QuickSort(TYPE *array, int low, int high)
{

    if (low < high) {
        int mid = PartitionVersion2(array, low, high);
        //        int mid = Partition(array, low, high);


        QuickSort(array, low, mid - 1);
        QuickSort(array, mid + 1, high);
    }
}


void QuickSortVersion2(TYPE *array, int low, int high)
{
    if (array == NULL || low >= high || low < 0 || high < 0)
        assert(-1);
    while (low < high) {
        int mid = PartitionVersion2(array, low, high);
        QuickSortVersion2(array, low, mid - 1);
        low = mid + 1;
    }
}

int Partition(TYPE *array, int low, int high)
{
    if (array == NULL || low >= high || low < 0 || high < 0)
        return -1;

    int mid_index =GetMiddle(array, low, high);

    TYPE mid = array[mid_index];
    swap(&array[low], &array[mid_index]);

    int left, right;
    left = low;
    right = left + 1;

    while (right <= high) {
        if (array[right] <= mid) {
            left++;
            if (left != right)
                swap(&array[left], &array[right]);

        }
    }

    swap(&array[low], &array[left]);
    return left;


}


int PartitionVersion2(TYPE *array, int low, int high)
{
    if (array == NULL || low >= high)
        assert(-1);


    int left, right;
    left = low;
    right = high;

    int mid_index =GetMiddle(array, low, high);

    TYPE mid = array[mid_index];
    swap(&array[low], &array[mid_index]);

    while (left < right) {
        while (array[right] > mid && left < right)
            right--;
        array[left] = array[right];

        while (array[left] <= mid && left < right)
            left++;

        array[right] = array[left];

    }

    array[left] = mid;
    return left;



}



int GetMiddle(TYPE *array, int low, int high)
{
    int mid = (low + high) / 2;
    if (array[mid] < array[high]) {
        if (array[low] > array[high])
            return high;
        else if (array[low] > array[mid])
            return low;
        else
            return mid;
    } else {
        if (array[low] > array[mid])
            return mid;
        else if (array[low] < array[high])
            return high;
        else
            return low;
    }

}

void swap(TYPE * num1, TYPE *num2)
{
    if (num1 != num2) {
        TYPE temp = *num1;
        *num1 = *num2;
        *num2 = temp;
    }
}



//for testing 
//  1 2 3 4 5 0 1 2 6 7
